/***************************************************************
*
* DSDEQUE.HPP
*
* Contains realization of double-sided queue. Based on allocating objects in center.
***************************************************************/

/***************************************************************
* dsDEQUE::dsDEQUE(void)
* 
***************************************************************/
template <typename T>
dsDEQUE<T>::dsDEQUE (void) :
   buffer         (NULL),
   head           (0),
   tail           (0),
   size           (0),
   allocated      (0)
{
   return;
}

/***************************************************************
* dsDEQUE::dsDEQUE (const dsDEQUE& src)
* 
***************************************************************/
template <typename T>
dsDEQUE<T>::dsDEQUE (const dsDEQUE& src) :
   buffer      (NULL),
   head        (src.head),
   tail        (src.tail),
   size        (src.size)
{  
   IncreaseBack (src.allocated);
   memmove(buffer, src.buffer, allocated*sizeof(T));
}

/***************************************************************
* dsDEQUE::dsDEQUE(size_t allocated)
* 
***************************************************************/
template <typename T>
dsDEQUE<T>::dsDEQUE (size_t allocated) :
   buffer         (NULL),
   head           (0),
   tail           (0),
   size           (0),
   allocated      (0)
{
   IncreaseBack (allocated);
   return;
}

/***************************************************************
* dsDEQUE::~dsDEQUE(void)
* 
***************************************************************/
template <typename T>
dsDEQUE<T>::~dsDEQUE (void)
{
   if (buffer != NULL) {
      delete buffer;
      buffer = NULL;
   }
}

/***************************************************************
* dsDEQUE::operator [](int i)
* 
***************************************************************/
template <typename T>
T& dsDEQUE<T>::operator [](int idx)
{
   size_t index = idx + head;
   assert(index >= head && index <= tail);
   return buffer[index];
}

/***************************************************************
* dsDEQUE::operator= (const dsDEQUE &that);
* 
***************************************************************/
template <typename T>
dsDEQUE<T>& dsDEQUE<T>::operator= (const dsDEQUE &src)
{
   if (&src == this){
      return *this;
   }
   
   allocated = src.allocated;
   head = src.head;
   tail = src.tail;
   size = src.size;
   
   if (buffer != NULL) {
      delete buffer;
   }

   buffer = new T [allocated];
   memmove(buffer, src.buffer, allocated*sizeof(T));

   return *this;
}

/***************************************************************
* dsDEQUE::PushFront (T item)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::PushFront (const T& val)
{
   if (head == 0) {
      IncreaseFront(allocated + 2);
   }

   if (head != 0 && size != 0) {
      --head;
   }

   buffer[head] = val;
   ++size;
}

/***************************************************************
* dsDEQUE::PushBack (T item)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::PushBack (const T& val)
{
   if (tail >= allocated - 1 || allocated == 0) {
      IncreaseBack(allocated + 2);
   }

   if (size != 0) {
      ++tail;
   }

   buffer[tail] = val;
   ++size;
}

/***************************************************************
* dsDEQUE::Resize (size_t size)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::Resize(size_t new_size) {
   IncreaseBack(new_size);
}

/***************************************************************
* dsDEQUE::Clear (void)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::Clear(void){
   if (buffer != NULL) {
      head        = 0;
      tail        = 0;
      size        = 0;
      allocated   = 0;
      delete buffer;
      buffer = NULL;
   }
}

/***************************************************************
* dsDEQUE::PopFront (T item)
* 
***************************************************************/
template <typename T>
T& dsDEQUE<T>::PopFront (void)
{
   assert (size != 0);
   T value = buffer[head];

   if (head < tail){
      ++head;
   }

   --size;
   return value;
}

/***************************************************************
* dsDEQUE::PopBack (T item)
* 
***************************************************************/
template <typename T>
T& dsDEQUE<T>::PopBack (void)
{
   assert (size != 0);
   T value = buffer[tail];

   if (tail > head){
      --tail;
   }

   --size;
   return value;
}

/***************************************************************
* dsDEQUE::GetFront (void)
* 
***************************************************************/
template <typename T>
T& dsDEQUE<T>::GetFront (void) const
{
   assert (!IsEmpty());
   return buffer[head];
}

/***************************************************************
* dsDEQUE::GetBack (void)
* 
***************************************************************/
template <typename T>
T& dsDEQUE<T>::GetBack (void) const
{
   assert (!IsEmpty());
   return buffer[tail];
}

/***************************************************************
* dsDEQUE::Find (const T& item) const
* 
***************************************************************/
template <typename T>
int dsDEQUE<T>::Find (const T& item) const{
   for (int i = head; i <= tail; ++i){
      if (buffer[i] == item){
         return i;
      }
   }

   return -1;
}

/***************************************************************
* dsDEQUE::IncreaseFront (void)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::IncreaseFront (size_t new_size) 
{
   T *pTempBuffer = new T [new_size];
   int offset = new_size - allocated;

   if (buffer != NULL){
      memmove (&pTempBuffer[offset], buffer, size*sizeof(T));   
      delete buffer;
   } else {
      --offset;
   }

   buffer = pTempBuffer;
   head = offset;
   tail += offset; 
   allocated = new_size;
}

/***************************************************************
* dsDEQUE::IncreaseBack (void)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::IncreaseBack (size_t new_size) 
{
   T *pTempBuffer = new T [new_size];

   if (buffer != NULL) {
      memmove (pTempBuffer, buffer, (head + size)*sizeof(T));
      delete buffer;
   }

   buffer = pTempBuffer;
   allocated = new_size; 
}

/***************************************************************
* dsDEQUE::DebugShow (void)
* 
***************************************************************/
template <typename T>
void dsDEQUE<T>::ShowDebug(void) 
{
   if (size == 0)
      return;
   for (int i = 0; i < head; ++i){
      printf (" * ");
   }
   for (int i = head; i <= tail; ++i){
      printf (" %i ", buffer[i]);
   }
   for (int i = tail + 1; i < allocated; ++i){
      printf (" * ");
   }
   printf ("\n");
}
//
// End-of-file DS_DEQUE.HPP
//